# 换硬币，[1,2,5] 最少多少个硬币可以拼成11
def coinChange(coins, amount):
    MAX = amount + 1
    dp = [MAX for _ in range(amount + 1)]
    dp[0] = 0
    for i in range(1, amount + 1):
        for j in range(0, len(coins)):
            if coins[j] <= i:
                dp[i] = min(dp[i], dp[i - coins[j]] + 1)
            print(dp, "i:", i, " j:", j)
    return -1 if dp[amount] > amount else dp[amount]


if __name__ == '__main__':
    print(coinChange([2, 5], 11))
